Abstract: This talk is based on a joint work with Soheil Behnezhad, Alma Ghafari, and Ronitt Rubinfeld, to appear in STOC'25, https://arxiv.org/abs/2411.08805.
We prove that a polynomial degree (in inverse of realization probability) subgraph can obtain a (1-epsilon)-approximation for stochastic mtaching, improving over the previous quasi-polynomial degree bound of [Behnezhad, Derakhshan, Hajiaghayi STOC'20].
Beyond its quantitative improvement, a key conceptual contribution of our work is to connect local computation algorithms (LCAs) to the stochastic matching problem for the first time. While prior work on LCAs mainly focuses on their out-queries (the number of vertices probed to produce the output of a given vertex), our analysis also bounds the in-queries (the number of vertices that probe a given vertex). We prove that the outputs of LCAs with bounded in- and out-queries (in-n-out LCAs for short) have limited correlation, a property that our analysis crucially relies on and might find applications beyond stochastic matchings.